package com.chj.jz.dp.class06;

//https://www.jiuzhang.com/problem/distinct-subsequences/#tag-lang-java
public class Code05_DistinctSubsequences {
	public static int numDistinct(String s, String t) {
		if (s.equals(t)) {
			return 1;
		}

		char[] s1 = s.toCharArray();
		char[] s2 = t.toCharArray();
		int m = s1.length;
		int n = s2.length;
		int old, now = 0;
		int[][] f = new int[2][n + 1];
		// 代表 s.substring(0 , i) 和 t.substring(0 ，j) 的最大distinct答案
		// for(int i = 0 ; i <= m ; i++){
		// f[i][0] = 1;
		// //t 为 “” s有一种变成 “” 全删了
		// }
		for (int i = 0; i <= m; i++) {
			old = now;
			now = 1 - now;
			
			for (int j = 0; j <= n; j++) {
				if (j == 0) {
					f[now][j] = 1;
					continue;
				}

				if (i == 0) {
					f[now][j] = 0;
					continue;
				}

				f[now][j] = f[old][j];

				if (s1[i - 1] == s2[j - 1]) {
					// 去前面s找有匹配的个数 只和当前的i 匹配
					f[now][j] += f[old][j - 1];
				}
				// else{ //去前面s找有匹配的个数
				// f[i][j] = f[i - 1][j];
				// }
			}
		}
		return f[now][n];

	}

	public static void main(String[] args) {
		// 输入: "ABCD" and "EDCA"
		{
			String str1 = "rabbbit";
			String str2 = "rabbit";
			System.out.println(numDistinct(str1, str2));
		}
		{
			String str1 = "abcd";
			String str2 = "";
			System.out.println(numDistinct(str1, str2));
		}
	}
}
